package com.echo.boot.structure.heap;

import com.echo.boot.structure.tree.printer.BinaryTrees;

import java.util.Comparator;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/6/18
 * Time: 8:31
 */
public class Main {
    public static void main(String[] args) {
        // 面试题
        // 在海里数据中找到 前 k 个 最大的数
        // 新建一个小顶堆
        // 扫描 n 个整数
        Integer[] data = {38, 79, 9, 13, 80, 88, 67, 62, 95, 56, 60, 8, 93, 55, 73, 35, 66, 100, 31, 78};

        BinaryHeap<Integer> heap = new BinaryHeap<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        // 前5个最大数
        int top = 5;
        for (int i = 0; i < data.length; i++) {
            if (heap.size < 5) {
                heap.add(data[i]);
            } else {
                // 比价堆顶元素,当前元素大于对顶,替换
                if (data[i] > heap.get()) {
                    heap.replace(data[i]);
                }
            }
        }

        BinaryTrees.print(heap);
    }
}
